<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>单向链表</title>
</head>
<body>
<script>
  function LinkedList() {

    function Node(data) {
      this.data = data;
      this.next = null
    }

    this.head = null;
    this.length = 0;

    // 1. 在链表末尾追加元素
    LinkedList.prototype.append = function (element) {
      let newNode = new Node(element);

      if (this.length === 0) {
        this.head = newNode
      } else {
        // 找最后一个节点
        let current = this.head;
        while (current.next) {
          current = current.next
        }
        // 将新元素赋值给最后一个节点的next
        current.next = newNode
      }
      this.length++
    };

    // 2. 在指定位置添加元素
    LinkedList.prototype.insert = function (position, element) {
      if (position > this.length || position < 0) {
        return false
      }
      let newNode = new Node(element);

      if (position === 0) {
        newNode.next = this.head;
        this.head = newNode
      } else {
        let index = 0;
        let current = this.head;
        let previous = null;
        while (index++ < position) {
          previous = current;
          current = current.next
        }
        newNode.next = current;
        previous.next = newNode
      }
      this.length++;
      return true
    };

    // 3. 获取指定位置的元素
    LinkedList.prototype.get = function (position) {
      if (position >= this.length || position < 0) {
        return null
      }

      let current = this.head;
      let index = 0;
      while (index++ < position) {
        current = current.next
      }
      return current.data
    };

    // 4. 获取指定元素的位置
    LinkedList.prototype.indexOf = function (element) {
      let current = this.head;
      let index = 0;

      while (current) {
        if (current.data === element) {
          return index
        }
        index++;
        current = current.next
      }
      return -1
    };

    // 修改指定位置元素
    LinkedList.prototype.update = function (position, element) {
      if (position >= this.length || position < 0) {
        return false
      }

      let current = this.head;
      let index = 0;
      while (index++ < position) {
        current = current.next
      }
      current.data = element;
      return true
    };

    LinkedList.prototype.removeAt = function (position) {
      if (position < 0 || position >= this.length) {
        return false
      }
      if (position === 0) {
        this.head = this.head.next
      } else {
        let index = 0;
        let current = this.head;
        let previous = null;
        while (index++ < position) {
          previous = current;
          current = current.next
        }
        previous.next = current.next
      }
      this.length--;
      return true
    };

    LinkedList.prototype.remove = function (element) {
      let position = this.indexOf(element)
      this.removeAt(position)
    };

    LinkedList.prototype.isEmpty = function () {
      return this.length === 0
    };

    LinkedList.prototype.size = function () {
      return this.length;
    };

    LinkedList.prototype.toString = function () {
      let current = this.head;
      let result = '';
      while (current) {
        result += current.data + ' ';
        current = current.next
      }
      return result
    }

  }

  let link = new LinkedList();
  link.append("zhangsan");
  link.append("lisi");
  link.append("wangwu");
  link.insert(3, 'zhaoliu');

  // link.removeAt(2)
  link.remove('zhaoliu');
  alert(link)
</script>
</body>
</html>